function Node(val, level) {
    this.value = val;
    this.level = level;
    this.next = null;
    this.down = null;
  }
  class SkipList {
    constructor(maxLevel) {
      this.maxLevel = maxLevel || 4;
      var heads = [];
      var below = null;
      for (var i = 0; i <= this.maxLevel; i++) {
        var node = new Node(-Infinity, i);// 我们要保证升序的结构，因此必须保证head最小
        heads.push(node);
        if (below) {
          node.down = below;// 建楼梯
        }
        below = node;
      }
      this.heads = heads;
    }
    insert(value) {
        var level = this.randomLevel();
        var node = this.heads[level];
        var upNode;
        while (true) {
          if (node.value == value) { // 命中
            // 已经存在对应结点则忽略，如果允许重复结点，我们可以为结点添加一个count属性，记录插入了多少次
            return false;
          }
          // 如果右边有结点，并且它比value小
          if (node.next && node.next.value <= value) { // 向右找
            node = node.next;
            continue;
          }
          // 没有往下找的分支，换成**插入**分支
          if (!node.next || node.next.value > value) {
            var next = node.next;
            var newNode = new Node(value, level);
            node.next = newNode;
            newNode.next = next;
            if (upNode) {
              upNode.down = newNode;// 修楼梯
            }
            upNode = newNode;
            level--; // 看还有没有下一层
            node = node.down || this.heads[level]; // 先走捷径，否则走最左边的结点
            if (node) {
              continue;
            } else {
              return false;
            }
          }
        }
        return true;
    }
    remove(value) {
        var node = this.heads[this.maxLevel], prev = node;
        while (true) {
          if (node.value == value) {// 命中
            var next = node.next;
            node.next = null;
            prev.next = next;// 移除当前楼层
            node = prev.down || this.heads[node.level - 1]; // 如果还存在下一层
            if (!node) {
              break;
            }
          }
          if (node.next && node.next.value <= value) {// 向右找
            prev = node;
            node = prev.next;
            continue;
          }
          if (node.down) {// 往下走
            node = node.down;
            continue;
          }
          break;
        }
    }
    find(value) {
        var node = this.heads[this.maxLevel];
        while (true) {
          if (node.value == value) {// 命中
            return true;
          }
          if (node.next && node.next.value <= value) { // 向右找
            node = node.next;
            continue;
          }
          if (node.down) {// 向下找
            node = node.down;
            continue;
          }
          return false;
        }
    }
    randomLevel() {
        var level = 0;
        for (var i = 0; i < this.maxLevel; i++) {
          level = Math.floor(Math.random() * (this.maxLevel + 1));
        }
        return level;
    }
    getSortedArray() {
      var array = [1, 3, 6, 7, 11, 15, 17].sort(function () {
        return Math.random > 0.5;
      });
      array.forEach(function (el) {
         s.insert(el);
      });
      return array;
    }
  }
  var s = new SkipList(2);
  console.log(s.getSortedArray());
  console.log(s);

